package one.linkList;

/**
 * 反转链表
 */
public class ReverseLinkedList {
    //时间复杂度O(n)
    //方式一：
    //思路：直接反转（n个节点，需要改n条边）
    //细节：next改为pre；预存next；移动cur（head）和next
    public static ListNode reverseList1(ListNode head) {
        //方式一：直接反转
        ListNode cur = head;
        ListNode next = null;
        ListNode pre = null;
        while(cur != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    //时间复杂度O(n)
    //方式二：
    //思路：使用帮助节点（n个节点，需要改n条边）
    //细节：next改为pre；预存next；移动cur（head）和next
    public static ListNode reverseList(ListNode head) {
        //方式二：使用帮助节点（不需要使用pre了）（相当于无帮助节点从第二个元素开始头插法建立链表）
        if(head == null) return null;
        ListNode helpHead = new ListNode(0, head);
        ListNode cur = head.next;
        ListNode next = null;
        head.next = null;
        while(cur != null){
            next = cur.next;
            cur.next = helpHead.next;
            helpHead.next = cur;
            cur = next;
        }
        return helpHead.next;
    }
}
class ListNode{
    int val;
    ListNode next;

    public ListNode(){}
    public ListNode(int val){
        this.val = val;
    }
    public ListNode(int val, ListNode next){
        this(val);
        this.next = next;
    }
}
